package com.zh.note.leetcode.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 51. N 皇后
 */
public class LC_51_solveNQueens {

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        char[][] chessBoard = new char[n][n];
        for (char[] c : chessBoard) {
            Arrays.fill(c, '.');
        }
        dfs(chessBoard, n, 0, res);
        return res;
    }

    // n 为输入的棋盘大小
    // row 是当前递归到棋盘的第几行了
    private void dfs(char[][] chessBoard, int n, int row, List<List<String>> res) {
        //终止条件
        if (row == n) {
            res.add(charArrayToList(chessBoard));
            return;
        }

        for (int i = 0; i < n; i++) {
            if (isValid(row, i, chessBoard, n)) {// 验证合法就可以放
                chessBoard[row][i] = 'Q';// 放置皇后
                dfs(chessBoard, n, row + 1, res);
                chessBoard[row][i] = '.';// 回溯，撤销皇后

            }
        }

    }

    /**
     * 判断皇后位置是否合法
     */
    private boolean isValid(int row, int col, char[][] chessBoard, int n) {
        // 检查列
        for (int i = 0; i < row; i++) { // 相当于剪枝
            if (chessBoard[i][col] == 'Q') {
                return false;
            }
        }
        // 检查45度对角线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (chessBoard[i][j] == 'Q') {
                return false;
            }
        }
        // 检查135度对角线
        for (int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--, j++) {
            if (chessBoard[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }

    /**
     * char数组转换成list
     */
    private List<String> charArrayToList(char[][] chessBoard) {
        List<String> list = new ArrayList<>();
        for (char[] chars : chessBoard) {
            list.add(String.valueOf(chars));
        }
        return list;
    }
}
